\section{Ciphertext only attacks on A5/2}

We have now seen how it is possible to recover the secret key in a known
plaintext attack. In this section we will show how \cite{bbk}
transformed the attack into a ciphertext only attack.

First they noted that GSM used error correction when transmitting messages. The
problem with the way they used the error correction is that the message is
encoded before it is encrypted. When doing it this way you are introducing
structured redundancy into the plaintext. It is that redundancy together with
the ciphertext\cite{bbk} that is being used in their attack. 

In the Slow Associated Control Channel (SACCH) that is used in the
initialization of a GSM session, the messages size is 184 bits. After 
error correction the message has grown to 456 bits, which is split 
into four frames that is encrypted using $A5/2$. 

Let $P$ be the message before encoding. It is possible to create a matrix, $G$
which is a $[456 \times 184]$ matrix in  $\mathbb{Z}\backslash
2\mathbb{Z}$. such that the encoding of $P$ is expressed as a matrix
multiplication:
\be{encoding}
	M = (G \cdot P)
\ee
$G$ is called a linear code \cite{linearcode}. These are often used in forward
error correction on communication channels like GSM.
To understand how this error correction works we let $n = 456$, that is the 
number of bits the message have after it is error corrected and let $k = 184$,
the information bits. Since $G^T$ is a matrix on the form $G = [I_k \vert C]$ 
where $I_k$ is the identity matrix and C is a $[k \times r]$ matrix where $r =
n - k$. This gives us a matrix on the form $[184 \times 456]$.

By the properties of such a linear code, a matrix $H$ exists such that:
\be{Hmatrix}
	H \cdot M = H \cdot (G \cdot P) = 0
\ee
where $H$ is called the parity check matrix \cite{parity}, and is used to ensure
that the message received in fact is the right message and that it does not
contain any errors. If the message contains errors the result of the multiplication would
have been a vector whit 1 on the entries where an error occurred.
\\
$M$ was our message so we may define our ciphertext $C$ as
$C = M \oplus k$ where $k = k_1 || k_2 || k_3 || k_4$ and $k_i$ is the
key-stream of the $i$'th frame.
\be{HandCipher}
\begin{split}
	H \cdot C &= H \cdot (M \oplus k)\\ 
			  &= H \cdot M \oplus H \cdot k\\ 
		 	  &= 0 \oplus H \cdot k\\ 
			  &= H \cdot k
\end{split}
\ee
We know $C$, this gives us a linear system of equations over the bits in
$k$. As shown in the previous section, it is possible to solve this system by
guessing the right value of $R4_1$. 

For each guess of $R4_1$ they substitute each bit in k in the equation system
with its description in terms of variables in $V_f$ where $V_f$ is the set of
variables used to represent the initial state of $R1_f$, $R1_f$, $R1_f$ after
liniazation. 

Now let $S_R4_1$ be the system's matrix and let $S_R4_1 \cdot V_f = k$ we can
now multiply by $H$ on both sides and get:
\be{multWithH}
	(H \cdot S_R4_1) \cdot V_f = H \cdot k
\ee
We then compute every possible $H \cdot S_R4_1$ before we launch the attack and
find linear dependencies in each of them and use these dependencies to filter
from values of $R4_f$ in the online phase of the attack.

From each encoding of 456 bit you get 272 equations, so after two messages, it
is possible to to solve the system of equations since we would have to get to
the initial state of the registers and reverse the key-setup to get the
$K_c$.

The redundancy that is introduced before the encryption by the use of error
correction is what is causing the problem. Had the error correction taken
place after the encryption, we would not have had any information about the
plaintext before the encryption, and would not had been able to create a linear
system of equations in order to get to the initial state of the registers.
